{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Times Binary String Is Prefix-Aligned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTimesAllBlue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制字符串前缀一致的次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 、下标从 <strong>1</strong> 开始的二进制字符串，所有位最开始都是 <code>0</code> 。我们会按步翻转该二进制字符串的所有位（即，将 <code>0</code> 变为 <code>1</code>）。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>1</strong> 开始的整数数组 <code>flips</code> ，其中 <code>flips[i]</code> 表示对应下标 <code>i</code> 的位将会在第 <code>i</code> 步翻转。</p>\n",
    "\n",
    "<p>二进制字符串 <strong>前缀一致</strong> 需满足：在第 <code>i</code> 步之后，在 <strong>闭</strong> 区间&nbsp;<code>[1, i]</code> 内的所有位都是 1 ，而其他位都是 0 。</p>\n",
    "\n",
    "<p>返回二进制字符串在翻转过程中 <strong>前缀一致</strong> 的次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>flips = [3,2,4,1,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>二进制字符串最开始是 \"00000\" 。\n",
    "执行第 1 步：字符串变为 \"00100\" ，不属于前缀一致的情况。\n",
    "执行第 2 步：字符串变为 \"01100\" ，不属于前缀一致的情况。\n",
    "执行第 3 步：字符串变为 \"01110\" ，不属于前缀一致的情况。\n",
    "执行第 4 步：字符串变为 \"11110\" ，属于前缀一致的情况。\n",
    "执行第 5 步：字符串变为 \"11111\" ，属于前缀一致的情况。\n",
    "在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>flips = [4,1,2,3]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>二进制字符串最开始是 \"0000\" 。\n",
    "执行第 1 步：字符串变为 \"0001\" ，不属于前缀一致的情况。\n",
    "执行第 2 步：字符串变为 \"1001\" ，不属于前缀一致的情况。\n",
    "执行第 3 步：字符串变为 \"1101\" ，不属于前缀一致的情况。\n",
    "执行第 4 步：字符串变为 \"1111\" ，属于前缀一致的情况。\n",
    "在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == flips.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>flips</code> 是范围 <code>[1, n]</code> 中所有整数构成的一个排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-times-binary-string-is-prefix-aligned](https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-times-binary-string-is-prefix-aligned](https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,1,5]', '[4,1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):  # i 从 1 开始\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        max_pos = 0\n",
    "        res = 0\n",
    "        for i in range(len(flips)):\n",
    "            if flips[i] > max_pos:\n",
    "                max_pos = flips[i]\n",
    "            if max_pos == i+1 :\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        l = len(flips)\n",
    "        s = [0] * l\n",
    "        tmp = 0\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            s[flips[i] - 1] = 1\n",
    "            if flips[i] - 1 < i:\n",
    "                tmp += 1\n",
    "            if s[i] == 1:\n",
    "                tmp += 1 \n",
    "            #print(tmp, s, i)\n",
    "            if tmp == i + 1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 记录翻转位置的最大值\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            # 会按步翻转该二进制字符串的所有位（即，将 0 变为 1）\n",
    "            right = max(right, flips[i])\n",
    "            if right == i + 1:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            cur = max(cur, flips[i-1])\n",
    "            if i == cur:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = 0\n",
    "        idx = 1\n",
    "        cur = 1\n",
    "        for num in flips:\n",
    "            if num > cur:\n",
    "                cur = num\n",
    "            if cur == idx:\n",
    "                ans += 1\n",
    "            idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            right = max(right, flips[i])\n",
    "            if right == i + 1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        # 已添加的数中最大的数 == i+1的时候\n",
    "        mx = ans = 0\n",
    "        for i, n in enumerate(flips):\n",
    "            if n > mx:\n",
    "                mx = n\n",
    "            if mx == i + 1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx,x)\n",
    "            ans += mx == i \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):  # i 从 1 开始\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i # 相当于if mx == i： ans += 1\n",
    "        return ans\n",
    "#如果第 i 步「前缀一致」，说明前 i 步的 flips[i] 恰好组成了 1 到 i 的所有数字。由于每一步只能翻转一个位置，此时必然满足「其他位都是0」的要求。\n",
    "#由于题目保证「flips是范围 [1,n]中所有整数构成的一个排列」，所以前 i 个数互不相同。如果前 i 个数的最大值等于 i，则说明找到了 [1,i]内的所有整数。（如果有一个数没找到，那这个数必然大于 i，与最大值等于 i 矛盾。）\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans=mx=0\n",
    "        for i,x in enumerate(flips,1):\n",
    "            mx=max(x,mx)\n",
    "            ans+=mx==i\n",
    "        return ans\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, n in enumerate(flips):\n",
    "            if n > mx:\n",
    "                mx = n\n",
    "            if i + 1 >= mx:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        max_pos, min_pos = 0, float('inf')\n",
    "        res = 0\n",
    "        for i in range(len(flips)):\n",
    "            if flips[i] > max_pos:\n",
    "                max_pos = flips[i]\n",
    "            if flips[i] < min_pos:\n",
    "                min_pos = flips[i]\n",
    "            if max_pos == i+1 and max_pos-min_pos == i:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n,ans,x=len(flips),0,0\n",
    "        for i in range(n):x=max(x,flips[i]-1);ans+=(x==i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans=mx=0\n",
    "        for i,x in enumerate(flips,1):\n",
    "            mx=max(x,mx)\n",
    "            ans+=mx==i\n",
    "        return ans\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n=len(flips)\n",
    "        total,count=0,0\n",
    "        for i in range(1,n+1):\n",
    "            total+=flips[i-1]\n",
    "            if i*(i+1)//2 ==total:\n",
    "                count+=1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class  Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            right = max(right, flips[i])\n",
    "            if right == i + 1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        m = 0\n",
    "        ans = 0\n",
    "        for i in range(len(flips)):\n",
    "            if flips[i] > m:\n",
    "                m = flips[i]\n",
    "            if m == i + 1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = dic = 0\n",
    "        for i,k in enumerate(flips):\n",
    "            dic = max(dic,k)\n",
    "            if dic == i + 1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numTimesAllBlue(self, flips) :\n",
    "    ans = r = 0\n",
    "    for index, item in enumerate(flips):\n",
    "      r = max(r, item)\n",
    "      if r == index + 1:\n",
    "        ans += 1\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 一、思考\n",
    "# 由于 [1,i][1,i][1,i] 内恰好有 iii 个整数，如果第 iii 步「前缀一致」，说明前 iii 步的 flips[i]\\textit{flips}[i]flips[i] 恰好组成了 111 到 iii 的所有数字。由于每一步只能翻转一个位置，此时必然满足「其他位都是 000」的要求。（例如示例 1 的前 444 个数和前 555 个数。）\n",
    "# 如何判断在第 iii 步是否找到了 [1,i][1,i][1,i] 内的所有整数呢？\n",
    "\n",
    "# 二、解惑\n",
    "# 由于题目保证「flips\\textit{flips}flips 是范围 [1,n][1,n][1,n] 中所有整数构成的一个排列」，所以前 iii 个数互不相同。如果前 iii 个数的最大值等于 iii，则说明找到了 [1,i][1,i][1,i] 内的所有整数。（如果有一个数没找到，那这个数必然大于 iii，与最大值等于 iii 矛盾。）\n",
    "\n",
    "# 三、算法\n",
    "# 遍历 flips\\textit{flips}flips，维护前 iii 个数的最大值 mx\\textit{mx}mx。如果 mx=i+1\\textit{mx} = i+1mx=i+1 就把答案加一。（注意代码中的数组下标需要从 000 开始，而题目描述是从 111 开始的。）\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        res = 0\n",
    "        maxNum = 0\n",
    "        for i, num in enumerate(flips, 1):\n",
    "            maxNum = max(maxNum, num)\n",
    "            res += i == maxNum\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "#         n = len(flips)\n",
    "#         a = [0] * n\n",
    "#         b = [0] * n\n",
    "#         res = 0\n",
    "#         for i in range(n):\n",
    "#             a[i] = 1\n",
    "#             b[flips[i] - 1] = 1\n",
    "#             if a == b:\n",
    "#                 res += 1\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for i, num in enumerate(flips):\n",
    "            cur = max(cur, num)\n",
    "            if i + 1 == cur:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        cnt = 0\n",
    "        num_sum = 0\n",
    "        for i in range(n):\n",
    "            num_sum += flips[i]\n",
    "            if  num_sum == (i+2)*(i+1)//2:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n=len(flips)\n",
    "        max_now=flips[0]\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            max_now=max(max_now,flips[i])\n",
    "            if max_now==i+1:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):  # i 从 1 开始\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        num_max = 0\n",
    "        for i,num in enumerate(flips):\n",
    "            num_max = max(num_max,num)\n",
    "            if num_max == i+1:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mm = -1\n",
    "        # n = len(flips)\n",
    "        for i,x in enumerate(flips,1):\n",
    "            mm = max(x,mm)\n",
    "            if mm == i:\n",
    "                ans += 1\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans=mx= 0\n",
    "        for i,x in enumerate(flips, 1):\n",
    "            mx=max(mx, x)\n",
    "            ans += (mx== i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        ref_num = 1\n",
    "        filp_max = 0\n",
    "        for i in flips:\n",
    "            filp_max = max(filp_max , i)\n",
    "            if filp_max == ref_num:\n",
    "                cnt += 1\n",
    "            ref_num += 1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            right = max(right, flip-1)\n",
    "            if i == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        maxSoFar = -1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            maxSoFar = max(maxSoFar, flips[i])\n",
    "            if maxSoFar == i+1:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        m, cnt = 0, 0\n",
    "        for i in range(1, len(flips) + 1):\n",
    "            m = max(flips[i-1], m)\n",
    "            if m == i:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        size = 0 \n",
    "        max_num = 0 \n",
    "        ans = 0 \n",
    "        for i in flips:\n",
    "            size += 1\n",
    "            max_num = max(max_num,i)\n",
    "            if size == max_num:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx,x)\n",
    "            ans += mx == i \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        maxPos = 1\n",
    "        while cur <= n:\n",
    "            if flips[cur - 1] >= cur:\n",
    "                maxPos = max(maxPos, flips[cur - 1])\n",
    "            if cur == maxPos:\n",
    "                ans += 1\n",
    "            cur += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        maxn = -1e9\n",
    "        for i in range(len(flips)):\n",
    "            maxn = max(maxn,flips[i])\n",
    "            if maxn == i+1:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        cnt = 0\n",
    "        num_sum = 0\n",
    "        for i in range(n):\n",
    "            num_sum += flips[i]\n",
    "            if  num_sum == (i+2)*(i+1)//2:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        u = 0\n",
    "        c = 0\n",
    "        m = 0\n",
    "        for i in flips:\n",
    "            m = max(i, m)\n",
    "            u = u | (1 << (i - 1))\n",
    "            v = u ^ ((u << 1) ^ (1 << m))\n",
    "            if v == 1:\n",
    "                c = c + 1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        res=mx=0\n",
    "        for i,x in enumerate(flips,1):\n",
    "            mx=max(mx,x)\n",
    "            res+=mx==i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        result = 0\n",
    "        before_lastest = 1\n",
    "        for i in range(len(flips)):\n",
    "            if (before_lastest is None) or (flips[i]>before_lastest):\n",
    "                before_lastest = flips[i]\n",
    "\n",
    "            if i+1>=before_lastest:\n",
    "                result += 1\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        minm = flips[0]\n",
    "        maxm = flips[0]\n",
    "        ans = 0\n",
    "        if minm == maxm == 1:\n",
    "            ans += 1\n",
    "        for i in range(1, len(flips)):\n",
    "            minm = min(minm, flips[i])\n",
    "            maxm = max(maxm, flips[i])\n",
    "            if minm == 1 and maxm - minm == i:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        m = -float('inf')\n",
    "        r = 0\n",
    "        for i in range(len(flips)):\n",
    "            m = max(m, flips[i])\n",
    "            if m == i+1:\n",
    "                r += 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):  # i 从 1 开始\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        compare = 0\n",
    "        original = 0\n",
    "        count = 0\n",
    "        for i, num in enumerate(flips):\n",
    "            original = original | (1<<(n-num))\n",
    "            compare = compare | (1<<(n-i-1))\n",
    "            # print(compare, original, (original>>(n-i-1)) ^ (compare>>(n-i-1)))\n",
    "            if (original>>(n-i-1)) ^ (compare>>(n-i-1)) == 0:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        max1=0\n",
    "        sums=0\n",
    "        for i in range(len(flips)):\n",
    "            max1=max(flips[i],max1)\n",
    "            print(max1,i+1)\n",
    "            if i+1==max1:\n",
    "                sums=sums+1\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cnt, n = 0, len(flips)\n",
    "        maxVal = 0\n",
    "        for i in range(n):\n",
    "            maxVal = max(maxVal, flips[i])\n",
    "            if maxVal == i + 1:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        pre = -1\n",
    "        ans=0\n",
    "        for i,f in enumerate(flips):\n",
    "            if pre ==-1:\n",
    "                tmp = f-1\n",
    "                pre = f\n",
    "            else:\n",
    "                if f<pre:\n",
    "                    tmp-=1\n",
    "                elif f>pre:\n",
    "                    tmp += (f-pre-1)\n",
    "                    pre = f\n",
    "            if tmp==0:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            right = max(right, flip-1)\n",
    "            if i == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        maximum=0\n",
    "        n=len(flips)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            maximum=max(maximum,flips[i])\n",
    "            if maximum==i+1:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        out = 0\n",
    "        l = len(flips)\n",
    "        tmp = [0] * l\n",
    "        goal = []\n",
    "        maxnum = flips[0]\n",
    "        for i in range(l):\n",
    "            tmp[flips[i]-1] = 1-tmp[flips[i]-1]\n",
    "            maxnum = max(maxnum,flips[i])\n",
    "            if i+1 == maxnum:\n",
    "                out += 1\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        cnt, n = 0, len(flips)\n",
    "        maxVal = 0\n",
    "        for i in range(n):\n",
    "            maxVal = max(maxVal, flips[i])\n",
    "            if maxVal == i + 1:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        count = 0\n",
    "        temp = 0\n",
    "        for i in range(len(flips)):\n",
    "            temp = max(temp, flips[i])\n",
    "            if temp == i+1:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans=l_int=0\n",
    "        for i,word in enumerate(flips):\n",
    "            l_int=max(l_int,word)\n",
    "            if l_int==i+1:\n",
    "                ans +=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        if len(flips) < 2:\n",
    "            return 1\n",
    "        res = 0\n",
    "        dp = [0] * len(flips)\n",
    "        dp[0], dp[1] = 1, 3\n",
    "        sum = flips[0]\n",
    "        if sum == dp[0]:\n",
    "            res += 1\n",
    "        sum += flips[1]\n",
    "        if sum == dp[1]:\n",
    "            res += 1\n",
    "        for i in range(2, len(flips)):\n",
    "            dp[i] = dp[i-1] + i + 1\n",
    "            sum += flips[i]\n",
    "            if dp[i] == sum:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = right = 0\n",
    "        for i, flip in enumerate(flips):\n",
    "            right = max(right, flip)\n",
    "            if right == i + 1:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(flips, 1):  # i 从 1 开始\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTimesAllBlue(self, flips: List[int]) -> int:\n",
    "        n = len(flips)\n",
    "        dp = [0] * (n+1)\n",
    "        cnt = 0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] +  flips[i-1]\n",
    "            if dp[i] == (1+i)*i//2:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
